{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #查找和最小的 K 对数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kSmallestPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找和最小的 K 对数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个以升序排列的整数数组 <code>nums1</code> 和<strong> </strong><code>nums2</code><strong>&nbsp;</strong>,&nbsp;以及一个整数 <code>k</code><strong>&nbsp;</strong>。</p>\n",
    "\n",
    "<p>定义一对值&nbsp;<code>(u,v)</code>，其中第一个元素来自&nbsp;<code>nums1</code>，第二个元素来自 <code>nums2</code><strong>&nbsp;</strong>。</p>\n",
    "\n",
    "<p>请找到和最小的 <code>k</code>&nbsp;个数对&nbsp;<code>(u<sub>1</sub>,v<sub>1</sub>)</code>, <code>&nbsp;(u<sub>2</sub>,v<sub>2</sub>)</code> &nbsp;... &nbsp;<code>(u<sub>k</sub>,v<sub>k</sub>)</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [1,7,11], nums2 = [2,4,6], k = 3\n",
    "<strong>输出:</strong> [1,2],[1,4],[1,6]\n",
    "<strong>解释: </strong>返回序列中的前 3 对数：\n",
    "    [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums1 = [1,1,2], nums2 = [1,2,3], k = 2\n",
    "<strong>输出: </strong>[1,1],[1,1]\n",
    "<strong>解释: </strong>返回序列中的前 2 对数：\n",
    "&nbsp;    [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums1 = [1,2], nums2 = [3], k = 3 \n",
    "<strong>输出:</strong> [1,3],[2,3]\n",
    "<strong>解释: </strong>也可能序列中所有的数对都被返回:[1,3],[2,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums1</code>, <code>nums2</code> 均为升序排列</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 373&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/\">https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [qn8gGX](https://leetcode.cn/problems/qn8gGX/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [qn8gGX](https://leetcode.cn/problems/qn8gGX/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        indexList = [0 for _ in nums2]\n",
    "        heap = [(nums1[0]+nums2[j],j) for j in range(len(nums2))]\n",
    "        re = []\n",
    "        heapq.heapify(heap)\n",
    "        for _ in range(k):\n",
    "            if not heap:\n",
    "                break\n",
    "            k = heapq.heappop(heap)\n",
    "            re.append((nums1[indexList[k[1]]],nums2[k[1]]))\n",
    "            if indexList[k[1]] < len(nums1) - 1:\n",
    "                indexList[k[1]] += 1\n",
    "                heapq.heappush(heap,(nums1[indexList[k[1]]]+nums2[k[1]],k[1]))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        pq=[]\n",
    "        m=len(nums1)\n",
    "        n=len(nums2)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if len(pq)<k:\n",
    "                    heapq.heappush(pq, (-nums1[i]-nums2[j], i, j))\n",
    "                else:\n",
    "                    if nums1[i]+nums2[j]<-pq[0][0]:\n",
    "                        heapq.heappop(pq)\n",
    "                        heapq.heappush(pq, (-nums1[i]-nums2[j], i, j))\n",
    "                    else:\n",
    "                        break\n",
    "        res=[]\n",
    "        for i in range(len(pq)):\n",
    "            res.append([nums1[pq[i][1]], nums2[pq[i][2]]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        m, n= len(nums1), len(nums2)\n",
    "        watched = [[False]*n for i in range(m)]\n",
    "\n",
    "        tool = []\n",
    "\n",
    "        heapq.heappush(tool, (nums1[0] + nums2[0], 0, 0))\n",
    "        watched[0][0] = True\n",
    "\n",
    "        while len(res)<k and len(tool)>0:\n",
    "            s, i1, i2 = heappop(tool)\n",
    "            res.append([nums1[i1], nums2[i2]])\n",
    "            if i1+1<len(nums1):\n",
    "                if not watched[i1+1][i2]:\n",
    "                    heapq.heappush(tool, (nums1[i1+1] + nums2[i2], i1+1, i2))\n",
    "                    watched[i1+1][i2] = True\n",
    "            \n",
    "            if i2+1<len(nums2):\n",
    "                if not watched[i1][i2+1]:\n",
    "                    heapq.heappush(tool, (nums1[i1] + nums2[i2+1], i1, i2+1))\n",
    "                    watched[i1][i2+1] = True\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n1,n2 = len(nums1),len(nums2)\n",
    "        used = [[False]*n2 for _ in range(n1)]\n",
    "        used[0][0] = True\n",
    "        heap = [(nums1[0]+nums2[0],0,0)]\n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            if not heap: break\n",
    "            _,i1,i2 = heappop(heap)\n",
    "            res.append([nums1[i1],nums2[i2]])\n",
    "            if i1 + 1 < len(nums1) and not used[i1+1][i2]:\n",
    "                heappush(heap,(nums1[i1+1]+nums2[i2],i1+1,i2))\n",
    "                used[i1+1][i2] = True\n",
    "            if i2 + 1 < len(nums2) and not used[i1][i2+1]:\n",
    "                heappush(heap,(nums1[i1]+nums2[i2+1],i1,i2+1))\n",
    "                used[i1][i2+1] = True\n",
    "        return res\n",
    "'''\n",
    "    1   1   2\n",
    "1   T\n",
    "2\n",
    "3\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        self.nums1 = nums1\n",
    "        self.nums2 = nums2\n",
    "        pair_cnt = self.binarySearch(k)\n",
    "\n",
    "        ans = []\n",
    "        p2 = len(self.nums2)-1\n",
    "        for val in self.nums1:\n",
    "\n",
    "            while p2 >=0 and val + self.nums2[p2] > pair_cnt: p2-=1\n",
    "            if p2 == -1: break\n",
    "            tmp = [ [val, val2] for val2 in nums2[:p2+1]]\n",
    "            ans.extend(tmp)\n",
    "\n",
    "        ans.sort(key=lambda x: sum(x))\n",
    "        return ans[:k]\n",
    "\n",
    "\n",
    "    def pairCnt(self, target):\n",
    "        \"\"\" \n",
    "        nums1 nums2 的组合 <= target 的数量\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        p2 = len(self.nums2)-1\n",
    "\n",
    "        for val in self.nums1:\n",
    "\n",
    "            while p2 >=0 and val + self.nums2[p2] > target: p2-=1\n",
    "            if p2 == -1: break\n",
    "            ans += p2+1\n",
    "\n",
    "        return ans\n",
    "    \n",
    "    def binarySearch(self, k):\n",
    "    \n",
    "        h = self.nums1[0] + self.nums2[0]\n",
    "        t = self.nums1[-1] + self.nums2[-1]\n",
    "\n",
    "        if k > self.pairCnt(t): return t+1\n",
    "\n",
    "        while h < t:\n",
    "            m = (h+t)//2\n",
    "            if k > self.pairCnt(m): h = m+1\n",
    "            else: t = m\n",
    "\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        l,r = nums1[0]+nums2[0],nums1[-1]+nums2[-1]+1\n",
    "        while r>l:\n",
    "            mid = (r+l)//2\n",
    "            t = sum(bisect_right(nums2,mid-i) for i in nums1)\n",
    "            if t==k:\n",
    "                break\n",
    "            elif t>k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        f = []\n",
    "        for i in nums1:\n",
    "            f += [[i,nums2[j]] for j in range(bisect_right(nums2,r-i))]\n",
    "        return sorted(f,key=lambda x:[sum(x),x])[:k]\n",
    "        # l,r = 0,0\n",
    "        # d1,d2 = defaultdict(int),defaultdict(int)\n",
    "        # # while l<len*()\n",
    "        # f = [[nums1[l],nums2[r]]]\n",
    "        # m,n = len(nums1),len(nums2)\n",
    "        # # d1[nums1[0]]+=1\n",
    "        # # while l<len(nums1)-1:\n",
    "        # #     d1[nums1[l+1]]+=1\n",
    "        # #     if nums1[l+1]==nums1[l]:\n",
    "        # #         nums1.pop(l+1)\n",
    "        # #     else:\n",
    "        # #         l+=1\n",
    "        # # d2[nums2[0]]+=1\n",
    "        # # while r<len(nums2)-1:\n",
    "        # #     d2[nums2[r+1]]+=1\n",
    "        # #     if nums2[r+1]==nums2[r]:\n",
    "        # #         nums2.pop(r+1)\n",
    "        # #     else:\n",
    "        # #         r+=1\n",
    "        # # l,r = 0,0\n",
    "        # # m,n = len(nums1),len(nums2)\n",
    "        # # f = [[nums1[l],nums2[r]]]*(d1[nums1[l]]*d2[nums2[r]])\n",
    "        # pl,pr= 0,0\n",
    "        # # print(nums1,nums2,d1,d2)\n",
    "        # while (l<m-1 or r<n-1) and len(f)<k:\n",
    "        #     mi = nums1[-1]+nums2[-1]+1\n",
    "        #     mid = None\n",
    "        #     if l==m-1:\n",
    "        #         pr = r+1\n",
    "        #     if r==n-1:\n",
    "        #         pl = l+1\n",
    "        #     if l<m-1:\n",
    "        #         t = bisect_left(nums2,nums2[r]-nums1[l+1]+nums1[l])\n",
    "        #         t = max(pr,t)\n",
    "        #         mi = nums1[l+1]+nums2[t]\n",
    "        #         mid = [l+1,t]\n",
    "        #     if r<n-1:\n",
    "        #         t = bisect_left(nums1,nums1[l]-nums2[r+1]+nums2[r])\n",
    "        #         t = max(pl,t)\n",
    "        #         if nums1[t]+nums2[r+1]<mi:\n",
    "        #             mi = nums1[t]+nums2[r+1]\n",
    "        #             mid = [t,r+1]\n",
    "        #     # r.append([])\n",
    "        #     l,r = mid\n",
    "        #     f+=[[nums1[l],nums2[r]]]#*(d1[nums1[l]]*d2[nums2[r]])\n",
    "        # return f[:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        q = []\n",
    "        res = []\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(len(nums2)):\n",
    "                heapq.heappush(q, (nums1[i] + nums2[j], [nums1[i], nums2[j]]))\n",
    "            next_sum = nums1[i+1] + nums2[0] if i+1 < len(nums1) else 1<<31\n",
    "            while q and q[0][0] <= next_sum:\n",
    "                res.append(q[0][1])\n",
    "                if len(res) == k: return res\n",
    "                heapq.heappop(q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class T:\n",
    "\n",
    "    def __init__(self, a, b, p):\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "        self.p = p\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return (self.a+self.b) <= (other.a+other.b)\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        import heapq\n",
    "\n",
    "        pq = []\n",
    "        for n in nums2:\n",
    "            heapq.heappush(pq, T(nums1[0], n, 0))\n",
    "        visit = [0]\n",
    "\n",
    "        ans = []\n",
    "        for _ in range(k):\n",
    "            if len(pq) == 0:\n",
    "                return ans\n",
    "\n",
    "            cur = heapq.heappop(pq)\n",
    "\n",
    "            ans.append([cur.a, cur.b])\n",
    "\n",
    "            temp = cur.p + 1\n",
    "            if temp < len(nums1) and temp not in visit:\n",
    "                for n in nums2:\n",
    "                    heapq.heappush(pq, T(nums1[temp], n, temp))\n",
    "                visit.append(temp)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "       r1,r2,l1,l2=0,0,1,1\n",
    "       ans=[[nums1[0]+nums2[0],nums1[0],nums2[0]]]\n",
    "       nums1.append(3e9)\n",
    "       nums2.append(3e9)\n",
    "       maxi=nums1[0]+nums2[0]\n",
    "       while(True):\n",
    "           if l1==len(nums1)-1 and l2==len(nums2)-1:\n",
    "               break \n",
    "           if r1==l1:\n",
    "               l2=l2+1\n",
    "               r1=0\n",
    "               if len(ans)>=10*k and nums1[r1]+nums2[l2]>=maxi:\n",
    "                   break\n",
    "           if r2==l2:\n",
    "                l1=l1+1\n",
    "                r2=0\n",
    "                if len(ans)>=10*k and nums1[l1]+nums1[r2]>=maxi:\n",
    "                    break \n",
    "           if nums1[l1]+nums2[r2]<=nums2[l2]+nums1[r1]:\n",
    "               heapq.heappush(ans,[nums1[l1]+nums2[r2],nums1[l1],nums2[r2]])\n",
    "               maxi=max(maxi,nums1[l1]+nums2[r2])\n",
    "               r2+=1\n",
    "           else:\n",
    "               heapq.heappush(ans,[nums1[r1]+nums2[l2],nums1[r1],nums2[l2]])\n",
    "               maxi=max(maxi,nums1[r1]+nums2[l2])\n",
    "               r1+=1\n",
    "       #print (ans)\n",
    "       if ans[-1][2]==3e9 or ans[-1][1]==3e9:\n",
    "            ans.pop()\n",
    "       r=[]\n",
    "       for i in range(k):\n",
    "            if not ans:\n",
    "               break\n",
    "            l=heapq.heappop(ans)\n",
    "            r.append(l[1:])\n",
    "       return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        start, end = nums1[0] + nums2[0], nums1[-1] + nums2[-1]\n",
    "        last = []\n",
    "        while(start <= end):\n",
    "            mid = (start + end) // 2\n",
    "            res = []\n",
    "            for i in range(len(nums1)):\n",
    "                for j in range(len(nums2)):\n",
    "                    if nums1[i] + nums2[j] <= mid:\n",
    "                        res.append([nums1[i], nums2[j]])\n",
    "                    else:\n",
    "                        break\n",
    "            if len(res) < k:\n",
    "                start = mid + 1\n",
    "            elif len(res) == k:\n",
    "                return res\n",
    "            else:\n",
    "                end = mid - 1\n",
    "            last = res\n",
    "        if len(last) > k:\n",
    "            last.sort(key= lambda tar: sum(tar))\n",
    "            return last[:k]\n",
    "        return last\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        def check(s):\n",
    "            cnt = 0\n",
    "            j = n-1\n",
    "            for i in range(m):\n",
    "                while j >= 0 and nums1[i] + nums2[j] > s:\n",
    "                    j -=1\n",
    "                if j < 0:\n",
    "                    break\n",
    "                cnt += j+1\n",
    "            return cnt >= k\n",
    "\n",
    "        lo, hi = 0, nums1[-1]+nums2[-1]\n",
    "        t = hi\n",
    "        while lo <= hi:\n",
    "            mid = (lo+hi)//2\n",
    "            if check(mid):\n",
    "                t = mid\n",
    "                hi = mid-1\n",
    "            else:\n",
    "                lo = mid+1\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            j = 0\n",
    "            while j < n and nums1[i] + nums2[j] <= t:\n",
    "                ans.append([nums1[i], nums2[j]])\n",
    "                j +=1\n",
    "        ans.sort(key=lambda x: x[0]+x[1])\n",
    "        return ans[:k]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        pq = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                pq.append((i, j))\n",
    "        heapq.heapify(pq)\n",
    "\n",
    "        return heapq.nsmallest(k, pq, key = lambda x:x[0]+x[1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        cache = [[(nums1[i], nums2[j]) for j in range(m)] for i in range(n)]\n",
    "        res = []\n",
    "        while cache and k > 0:\n",
    "            cur = 10**10\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(cache):\n",
    "                if sum(cache[i][0]) < cur:\n",
    "                    cur = sum(cache[i][0])\n",
    "                    j = i\n",
    "                i += 1\n",
    "            res.append(cache[j][0])\n",
    "            k -= 1\n",
    "            cache[j].pop(0)\n",
    "            if not cache[0]:\n",
    "                cache.pop(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        hq = []\n",
    "        for i in range(m):\n",
    "            num1 = nums1[i]\n",
    "            for j in range(n):\n",
    "                num2 = nums2[j]\n",
    "                hq.append((num1, num2))\n",
    "        \n",
    "        topK_items = heapq.nsmallest(k, hq, key = lambda x: x[0] + x[1])\n",
    "        return topK_items\n",
    "\n",
    "# class Solution:\n",
    "#     def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "#         m, n = len(nums1), len(nums2)\n",
    "#         ans = []\n",
    "#         pq = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, m))]\n",
    "#         while pq and len(ans) < k:\n",
    "#             _, i, j = heapq.heappop(pq)\n",
    "#             ans.append([nums1[i], nums2[j]])\n",
    "#             if j + 1 < n:\n",
    "#                 heapq.heappush(pq, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "#         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        all = []\n",
    "        for first in nums1:\n",
    "            for second in nums2:\n",
    "                all.append([first, second])\n",
    "\n",
    "        return heapq.nsmallest(k, all, key=lambda x: x[0] + x[1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        combine = []\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                combine.append([n1, n2])\n",
    "        \n",
    "        heap = []\n",
    "        for i in range(len(combine)):\n",
    "            heapq.heappush(heap, (-combine[i][0]-combine[i][1], i))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        \n",
    "        return [combine[x[1]] for x in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        h = [] # 堆\n",
    "        \n",
    "        if len(nums1) > k:\n",
    "            nums1 = nums1[:k]\n",
    "        if len(nums2) > k:\n",
    "            nums2 = nums2[:k]\n",
    "   \n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                heapq.heappush(h,[n1,n2])\n",
    "        \n",
    "        # 根据题目要求返回和最小的k个数对，给定key\n",
    "        res = heapq.nsmallest(k,h,key=lambda x:(x[0]+x[1]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution(object):\n",
    "    def kSmallestPairs(self, nums1, nums2, k):\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        sumMat = np.zeros((m, n))\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sumMat[i, j] = nums1[i] + nums2[j]\n",
    "        \n",
    "        sumVec = sumMat.flatten()\n",
    "        sortedIndices = np.argsort(sumVec)\n",
    "        minKIndex = sortedIndices[:k]\n",
    "        \n",
    "        result = []\n",
    "        for idx in minKIndex:\n",
    "            i, j = np.unravel_index(idx, (m, n))\n",
    "            result.append((nums1[i], nums2[j]))\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        arr = [[i, j] for i in nums1 for j in nums2]\n",
    "        res = heapq.nsmallest(k, arr, key=lambda x: sum(x))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import product\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        p = product(nums1[:k], nums2[:k])\n",
    "        p = [(-_[0]-_[1], _[0], _[1]) for _ in p]\n",
    "        h = []\n",
    "        for item in p:\n",
    "            if len(h) == k and item[0] > h[0][0]:\n",
    "                heapq.heappushpop(h, item)\n",
    "            if len(h) < k:\n",
    "                heapq.heappush(h, item)\n",
    "            \n",
    "        return [(pair[1], pair[2]) for pair in heapq.nlargest(k, h)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        priorityList = []\n",
    "        for (j, value) in enumerate(nums2):\n",
    "            heapq.heappush(priorityList, (nums1[0]+value, nums1[0], value))\n",
    "        res = []\n",
    "        enumNums1Idx = 0\n",
    "        while priorityList and k:\n",
    "            minValTuple = heapq.heappop(priorityList)\n",
    "            k -= 1\n",
    "            (_, val1, val2) = minValTuple\n",
    "            res.append([val1, val2])\n",
    "            nextIdx = enumNums1Idx + 1\n",
    "            if nextIdx < len(nums1):\n",
    "                for (j, value) in enumerate(nums2):\n",
    "                    heapq.heappush(priorityList, (nums1[nextIdx]+value, nums1[nextIdx], value))\n",
    "                enumNums1Idx += 1\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        results = []\n",
    "        for i in range(min(k, len(nums1))):\n",
    "            for j in range(min(k - i, len(nums2))):\n",
    "                results.append((nums1[i] + nums2[j], nums1[i], nums2[j]))\n",
    "        results.sort()\n",
    "        r = []\n",
    "        for i in range(min(k, len(results))):\n",
    "            r.append([results[i][1], results[i][2]])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        size1=len(nums1);size2=len(nums2)\n",
    "        lst=[]\n",
    "        for i in range(size1):\n",
    "            for j in range(size2):\n",
    "                heapq.heappush(lst,(nums1[i],nums2[j],-nums1[i]-nums2[j]))\n",
    "        ans=heapq.nlargest(k,lst,key=lambda x:x[2])\n",
    "        return [x[:2] for x in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        import heapq\n",
    "        i, j = 0, 0\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        h = []\n",
    "        ans = []\n",
    "        cnt = 1\n",
    "        while 1:\n",
    "            if i<n1 and j<n2:\n",
    "                heapq.heappush(h, (nums1[i]+nums2[j], nums1[i], nums2[j]))\n",
    "            if i<n1:\n",
    "                for jj in range(j+1, n2):\n",
    "                    heapq.heappush(h, (nums1[i]+nums2[jj], nums1[i], nums2[jj]))\n",
    "            if j<n2:\n",
    "                for ii in range(i+1, n1):\n",
    "                    heapq.heappush(h, (nums1[ii]+nums2[j], nums1[ii], nums2[j]))\n",
    "            if len(h) == 0:\n",
    "                return ans\n",
    "            cur = heapq.heappop(h)\n",
    "            ans.append(list(cur[1:]))\n",
    "            if cnt == k:\n",
    "                return ans\n",
    "            i += 1\n",
    "            j += 1\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # m, n = len(nums1), len(nums2)\n",
    "        # ans = []\n",
    "        # pq = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, m))]\n",
    "        # while pq and len(ans) < k:\n",
    "        #     _, i, j = heappop(pq)\n",
    "        #     ans.append([nums1[i], nums2[j]])\n",
    "        #     if j + 1 < n:\n",
    "        #         heappush(pq, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "        # return ans\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        minheap = []\n",
    "        for s1 in nums1:\n",
    "            for s2 in nums2:\n",
    "                heapq.heappush(minheap, (s1 + s2, s1, s2))\n",
    "        res = []\n",
    "        while len(res) < k and minheap:\n",
    "            _, i, j = heapq.heappop(minheap)\n",
    "            res. append([i, j])\n",
    "        return res\n",
    "\n",
    "\n",
    "        # heap, ans = [], []\n",
    "        # n1, n2 = len(nums1), len(nums2)\n",
    "        # heapq.heappush(heap, (nums1[0]+nums2[0], [nums1[0], nums2[0]], [0, 0]))\n",
    "\n",
    "        # while heap and len(ans) < k:\n",
    "        #     _, pair, [i, j] = heapq.heappop(heap)\n",
    "        #     ans.append(pair)\n",
    "        #     if i == 0 and j+1 < n2:\n",
    "        #         heapq.heappush(heap, (nums1[0]+nums2[j+1], [nums1[0], nums2[j+1]], [0, j+1]))\n",
    "        #     if i+1 < n1:\n",
    "        #         heapq.heappush(heap, (nums1[i+1]+nums2[j], [nums1[i+1], nums2[j]], [i+1, j]))\n",
    "\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        pq = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                heapq.heappush(pq, (i + j, i, j))\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if not pq:\n",
    "                break\n",
    "            item = heapq.heappop(pq)\n",
    "            ans.append([item[1], item[2]])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        tmp = []\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(len(nums2)):\n",
    "                tmpsum = nums1[i] + nums2[j]\n",
    "                heapq.heappush(tmp, (tmpsum, nums1[i], nums2[j]))\n",
    "            if i > k: break\n",
    "\n",
    "        ans = []\n",
    "        while(len(tmp)):\n",
    "            item = heapq.heappop(tmp)\n",
    "            ans.append([item[1], item[2]])\n",
    "        return ans[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        range1 = min(len(nums1),k)\n",
    "        range2 = min(len(nums2),k)\n",
    "        result = []\n",
    "        for i in range(range1):\n",
    "            for j in range(range2):\n",
    "                result.append((nums1[i],nums2[j]))\n",
    "        \n",
    "        result.sort(key = lambda x : x[0] + x[1])\n",
    "        return result[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import product\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        p = product(nums1[:k], nums2[:k])\n",
    "        p = [(_[0]+_[1], _[0], _[1]) for _ in p]\n",
    "        ans = sorted(p, key=lambda x: x[0])\n",
    "        return [[i[1], i[2]] for index, i in enumerate(ans) if index < k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # 首先获取所有的对数\n",
    "        num_list = list()\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                temp = (i+j, i, j)\n",
    "                num_list.append(temp)\n",
    "        num_list = sorted(num_list, key=lambda x:x[0])\n",
    "        # 以上获取了所有的队列只是队列中第一个元素是一个总和\n",
    "        heap_list = list()\n",
    "        for val in num_list:\n",
    "            if len(heap_list) == k:\n",
    "                if heap_list[0][0] > val[0]:\n",
    "                    heapq.heappop(heap_list)\n",
    "                    # 在入堆\n",
    "                    heapq.heappush(heap_list, val)\n",
    "            else:\n",
    "                heapq.heappush(heap_list, val)\n",
    "        # 以上就保持了出现的和最小\n",
    "        ret_list = [[i[1], i[2]] for i in heap_list]\n",
    "\n",
    "        return ret_list        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        \"\"\"暴力破解，排序取前 k 个组合\"\"\"\n",
    "        res = []\n",
    "        for num1 in nums1:\n",
    "            for num2 in nums2:\n",
    "                res.append([num1, num2])\n",
    "        res.sort(key=lambda x: sum(x))\n",
    "        return res[:k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        h = [[item1+item2, item1, item2] for item1 in nums1 for item2 in nums2]\n",
    "        heapq.heapify(h)\n",
    "        for _ in range(k):\n",
    "            if not h:\n",
    "                break\n",
    "            else:\n",
    "                item = heapq.heappop(h)\n",
    "                res.append(item[1:])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        uv_list = []\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                uv_list.append([n1, n2])\n",
    "        uv_list.sort(key=lambda x: x[0] + x[1])\n",
    "        return uv_list[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        \n",
    "        hq = []\n",
    "        for x in nums1:\n",
    "            for y in nums2:\n",
    "                heappush(hq, [x+y, x, y])\n",
    "        \n",
    "        # print(hq)\n",
    "        ans = []\n",
    "        while k and hq:\n",
    "            _, x, y = heappop(hq)\n",
    "            # print(x, y)\n",
    "            ans.append([x, y])\n",
    "            k-=1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        num_pair=[]\n",
    "        for num1 in nums1:\n",
    "            for num2 in nums2:\n",
    "                num_pair.append([num1,num2])\n",
    "        num_pair=sorted(num_pair,key=lambda x:x[0]+x[1])\n",
    "        res=[]\n",
    "        for i in range(len(num_pair)):\n",
    "            if i<k:\n",
    "                res.append(num_pair[i])\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ans = [[m,n] for m in nums1 for n in nums2]\n",
    "        ans = sorted(ans,key =lambda x:x[0]+x[1])\n",
    "        return ans[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        return sorted([[i, j] for i, j in product(nums1[:1000], nums2[:1000])], key=sum)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1, nums2, k: int):\n",
    "        answer, ans = [], []\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(len(nums2)):\n",
    "                answer.append([nums1[i], nums2[j], nums1[i] + nums2[j]])\n",
    "        answer.sort(key=lambda x: x[2])\n",
    "        if len(answer) < k:\n",
    "            for i in range(len(answer)):\n",
    "                ans.append([answer[i][0], answer[i][1]])\n",
    "        else:\n",
    "            for i in range(k):\n",
    "                ans.append([answer[i][0], answer[i][1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        temp = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                temp.append([i, j])\n",
    "        cmp = lambda x, y:1 if x[0]+x[1] > y[0]+y[1] else -1\n",
    "        temp.sort(key=cmp_to_key(cmp))\n",
    "        return temp[0: k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        def cmp(l1: list, l2: list):\n",
    "            if sum(l1) > sum(l2):\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans.append([nums1[i], nums2[j]])\n",
    "        ans = sorted(ans, key=functools.cmp_to_key(cmp))\n",
    "\n",
    "        return ans[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        total = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                total.append([i,j,i+j])\n",
    "        lst = sorted(total, key = lambda x: x[2])\n",
    "        res = []\n",
    "        for i in range(min(k,len(lst))):\n",
    "            res.append(lst[i][:2])\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for val1 in nums1:\n",
    "            for val2 in nums2:\n",
    "                res.append([val1, val2])\n",
    "        res = list(sorted(res, key = lambda x: x[0] + x[1]))\n",
    "        print(res)\n",
    "        return res[: k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        p,q = 0,0\n",
    "        heap = []\n",
    "        num = 0\n",
    "        while (p < m or q < n) and num < k:\n",
    "\n",
    "            if p < m:\n",
    "                while q < n:\n",
    "                    print(nums1[p],nums2[q])\n",
    "                    heapq.heappush(heap,(nums1[p] + nums2[q],[nums1[p],nums2[q]]))\n",
    "                    q += 1\n",
    "            q = p \n",
    "            p+=1\n",
    "            if q < n:\n",
    "                while p < m:\n",
    "                    print(nums1[p],nums2[q])\n",
    "                    heapq.heappush(heap,(nums1[p] + nums2[q],[nums1[p],nums2[q]]))\n",
    "                    p += 1\n",
    "            p = q\n",
    "            p += 1\n",
    "            q += 1\n",
    "            num += 3\n",
    "        return [heapq.heappop(heap)[1] for _ in range(min(k,len(heap)))]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        h = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                heapq.heappush(h, (i+j, (i, j)))\n",
    "        \n",
    "        pop_num = min(len(h), k)\n",
    "        res = []\n",
    "        while pop_num > 0:\n",
    "            s, p = heapq.heappop(h)\n",
    "            res.append([p[0], p[1]])\n",
    "            pop_num -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        all_list = []\n",
    "        for i in nums1[:k]:\n",
    "            for j in nums2[:k]:\n",
    "                all_list.append((i+j,(i,j)))\n",
    "\n",
    "        heapq.heapify(all_list)\n",
    "        ret_list = heapq.nsmallest(k, all_list)\n",
    "        ret = []\n",
    "        for z in ret_list:\n",
    "            ret.append(z[1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Pair:\n",
    "    def __init__(self, a, b):\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "    def __lt__(self, other):\n",
    "        return self.a + self.b <= other.a+other.b\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        pq = []\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        for i in range(min(m, k)):\n",
    "            for j in range(min(n, k)):\n",
    "                heapq.heappush(pq, Pair(nums1[i], nums2[j]))\n",
    "        while k > 0 and pq:\n",
    "            cur = heapq.heappop(pq)\n",
    "            ans.append([cur.a, cur.b])\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue  #优先级队列，优先级高的先输出\n",
    "class CompareAble:\n",
    "    def __init__(self,a, b):\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        res = self.a + self.b - other.a - other.b\n",
    "        if res >= 0:\n",
    "            return False\n",
    "        return True\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        len1 = len(nums1)\n",
    "        len2 = len(nums2)\n",
    "        MyQueue = PriorityQueue()\n",
    "        for i in range(len1):\n",
    "            for j in range(len2):\n",
    "                MyQueue.put(CompareAble(nums1[i], nums2[j]))\n",
    "        i = 0\n",
    "        res = []\n",
    "        while MyQueue.qsize() > 0 and i < k:\n",
    "            tmp = MyQueue.get()\n",
    "            i += 1\n",
    "            res.append([tmp.a, tmp.b])\n",
    "          #  print(tmp.a, tmp.b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import insort_left\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        st = []\n",
    "\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                insort_left(st, (n1 + n2, (n1, n2)))\n",
    "\n",
    "        return [_[1] for _ in st[:k]] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        key_value = []\n",
    "        res = []\n",
    "        n, m = len(nums1), len(nums2)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                heapq.heappush(key_value, (nums1[i] + nums2[j], [nums1[i], nums2[j]]))\n",
    "        for  i in range(min(k, m*n)):\n",
    "            x = heapq.heappop(key_value)[1]\n",
    "            res.append(x)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        q = []\n",
    "        cnt = 0\n",
    "        # d = set()\n",
    "        for v in nums1:\n",
    "            # d = set()\n",
    "            for x in nums2:\n",
    "                s = v + x\n",
    "                heapq.heappush(q, (s, (v, x)))\n",
    "        res = []\n",
    "        q.sort(key = lambda x: x[0])\n",
    "        for i in range(min(len(q), k)):\n",
    "            tmp = heapq.heappop(q)\n",
    "            res.append([tmp[1][0], tmp[1][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        nums1, nums2 = nums1[:k], nums2[:k]\n",
    "        pq = []\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                heappush(pq, (n1+n2, [n1, n2]))\n",
    "        res = []\n",
    "        while k and len(pq):\n",
    "            res.append(heappop(pq)[1])\n",
    "            k -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        # 和最小，不考虑两个元素的顺序就行\n",
    "        # 因为要k个对，所以只组合nums1和nums2的前k个就够了\n",
    "        # 使用堆，python中只有最小堆\n",
    "        cur = []\n",
    "        for i in nums1[:k]:\n",
    "            for j in nums2[:k]:\n",
    "                cur.append((-i-j, [i, j]))\n",
    "        heapK = []\n",
    "        for this in cur:\n",
    "            if k > 0:\n",
    "                heapq.heappush(heapK, this)\n",
    "                k -= 1\n",
    "            else:\n",
    "                if -heapK[0][0] > -this[0]:\n",
    "                    heapq.heappop(heapK)\n",
    "                    heapq.heappush(heapK, this)\n",
    "        res = []\n",
    "        for this in heapK:\n",
    "            res.append(this[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        items = []\n",
    "        n, m = len(nums1), len(nums2)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                items.append((-(nums1[i]+ nums2[j]), [nums1[i], nums2[j]]))\n",
    "\n",
    "        h = items[:k]\n",
    "        heapq.heapify(h)\n",
    "\n",
    "        for item in items[k:]:\n",
    "            heapq.heappushpop(h, item)\n",
    "        \n",
    "        ans = [item[1] for item in h]\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        from queue import PriorityQueue\n",
    "\n",
    "        q = PriorityQueue()\n",
    "\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                q.put((n1+n2,[n1,n2]))\n",
    "\n",
    "        count = 0\n",
    "        result = []\n",
    "        q_len = q.qsize()\n",
    "        while count<k and count<q_len:\n",
    "            sum,seq = q.get()\n",
    "            result.append(seq)\n",
    "            count += 1\n",
    "\n",
    "\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        temp = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                temp.append((i+j,i,j))\n",
    "        temp.sort(key=lambda x:x[0])\n",
    "        temp = [[x[1],x[2]] for x in temp]\n",
    "        return(temp[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class P:\n",
    "    def __init__(self, a, b, sum):\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "        self.sum = sum\n",
    "    def __lt__(self, other):\n",
    "        if self.sum < other.sum:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        heap = list([])\n",
    "        l1 = min(k,len(nums1))\n",
    "        l2 = min(k,len(nums2))\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                heap.append(P(nums1[i],nums2[j],nums1[i]+nums2[j]))\n",
    "        heapq.heapify(heap)\n",
    "        res = []\n",
    "        l3 = min(k,len(heap))\n",
    "        for _ in range(l3):\n",
    "            a = heapq.heappop(heap)\n",
    "            res.append([a.a,a.b])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:\n",
    "        pair = []\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                pair.append([n1, n2])\n",
    "        heap = []\n",
    "        for p in pair:\n",
    "            heapq.heappush(heap, (-(p[1]+p[0]), p))\n",
    "        while len(heap) > k:\n",
    "            heapq.heappop(heap)\n",
    "        ans = []\n",
    "        for h in heap:\n",
    "            ans.append(h[1])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
